package pers.qianyu.month_202012.date_20201225.dp_bag;

import pers.qianyu.util.*;

import java.util.*;

/**
 * 800. 背包问题 IX
 * https://www.lintcode.com/problem/backpack-ix/description
 *
 * @author mizzle rain
 * @date 2020-12-25 17:59
 */
public class BackpackIX {
    /**
     * @param n:           Your money
     * @param prices:      Cost of each university application
     * @param probability: Probability of getting the University's offer
     * @return: the  highest probability
     */
    public double backpackIX(int n, int[] prices, double[] probability) {
        double[] dp = new double[n + 1];
        Arrays.fill(dp, 1.0);
        for (int i = 0; i < probability.length; i++) {
            probability[i] = 1 - probability[i];
        }
        for (int i = 0; i < prices.length; i++) {
            int price = prices[i];
            double pro = probability[i];
            for (int j = n; j >= price; j--) {
                dp[j] = Math.min(dp[j], dp[j - price] * pro);
            }
            ArrayUtil.printArrayAsMarkdownTable(
                    String.format("重量：%s 价值%s", price, pro), dp, 2);
        }
        return 1 - dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        int[] prices = {4, 4, 5};
        double[] probability = {0.1, 0.2, 0.3};
        double result = new BackpackIX().backpackIX(n, prices, probability);
        System.out.println("result = " + result);
    }
}
